#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

class WorldPeace {
public:
	long long numGroups(int, vector <int>);
};

long long WorldPeace::numGroups(int k, vector <int> c) {
	long long hi = 10000000000000000LL;
	long long lo = 0LL;
	while(hi > lo){
		long long mid = (hi + lo + 1) / 2;
		long long sum = 0LL;
		for(int i=0; i<c.size(); i++){
			sum += c[i]<mid ? c[i]:mid;
		}
		if(sum < mid * k) hi = mid-1;
		else lo = mid;
	}
	return hi;
}


double test0() {
	int p0 = 4;
	int t1[] = { 4,4,4,4,4 };
	vector <int> p1(t1, t1+sizeof(t1)/sizeof(int));
	WorldPeace * obj = new WorldPeace();
	clock_t start = clock();
	long long my_answer = obj->numGroups(p0, p1);
	clock_t end = clock();
	delete obj;
	cout <<"Time: " <<(double)(end-start)/CLOCKS_PER_SEC <<" seconds" <<endl;
	long long p2 = 5LL;
	cout <<"Desired answer: " <<endl;
	cout <<"\t" << p2 <<endl;
	cout <<"Your answer: " <<endl;
	cout <<"\t" << my_answer <<endl;
	if (p2 != my_answer) {
		cout <<"DOESN'T MATCH!!!!" <<endl <<endl;
		return -1;
	}
	else {
		cout <<"Match :-)" <<endl <<endl;
		return (double)(end-start)/CLOCKS_PER_SEC;
	}
}
double test1() {
	int p0 = 5;
	int t1[] = { 1,2,3,4,5,6 };
	vector <int> p1(t1, t1+sizeof(t1)/sizeof(int));
	WorldPeace * obj = new WorldPeace();
	clock_t start = clock();
	long long my_answer = obj->numGroups(p0, p1);
	clock_t end = clock();
	delete obj;
	cout <<"Time: " <<(double)(end-start)/CLOCKS_PER_SEC <<" seconds" <<endl;
	long long p2 = 3LL;
	cout <<"Desired answer: " <<endl;
	cout <<"\t" << p2 <<endl;
	cout <<"Your answer: " <<endl;
	cout <<"\t" << my_answer <<endl;
	if (p2 != my_answer) {
		cout <<"DOESN'T MATCH!!!!" <<endl <<endl;
		return -1;
	}
	else {
		cout <<"Match :-)" <<endl <<endl;
		return (double)(end-start)/CLOCKS_PER_SEC;
	}
}
double test2() {
	int p0 = 2;
	int t1[] = { 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000 };
	vector <int> p1(t1, t1+sizeof(t1)/sizeof(int));
	WorldPeace * obj = new WorldPeace();
	clock_t start = clock();
	long long my_answer = obj->numGroups(p0, p1);
	clock_t end = clock();
	delete obj;
	cout <<"Time: " <<(double)(end-start)/CLOCKS_PER_SEC <<" seconds" <<endl;
	long long p2 = 3000000000LL;
	cout <<"Desired answer: " <<endl;
	cout <<"\t" << p2 <<endl;
	cout <<"Your answer: " <<endl;
	cout <<"\t" << my_answer <<endl;
	if (p2 != my_answer) {
		cout <<"DOESN'T MATCH!!!!" <<endl <<endl;
		return -1;
	}
	else {
		cout <<"Match :-)" <<endl <<endl;
		return (double)(end-start)/CLOCKS_PER_SEC;
	}
}
double test3() {
	int p0 = 7;
	int t1[] = { 96, 17, 32, 138, 112, 50, 7, 19, 412, 23, 14, 50, 47, 343, 427, 22, 39 };
	vector <int> p1(t1, t1+sizeof(t1)/sizeof(int));
	WorldPeace * obj = new WorldPeace();
	clock_t start = clock();
	long long my_answer = obj->numGroups(p0, p1);
	clock_t end = clock();
	delete obj;
	cout <<"Time: " <<(double)(end-start)/CLOCKS_PER_SEC <<" seconds" <<endl;
	long long p2 = 166LL;
	cout <<"Desired answer: " <<endl;
	cout <<"\t" << p2 <<endl;
	cout <<"Your answer: " <<endl;
	cout <<"\t" << my_answer <<endl;
	if (p2 != my_answer) {
		cout <<"DOESN'T MATCH!!!!" <<endl <<endl;
		return -1;
	}
	else {
		cout <<"Match :-)" <<endl <<endl;
		return (double)(end-start)/CLOCKS_PER_SEC;
	}
}
double test4() {
	int p0 = 10;
	int t1[] = { 638074479, 717901019, 910893151, 924124222, 991874870, 919392444, 729973192, 607898881, 
  838529741, 907090878, 632877562, 678638852, 749258866, 949661738, 784641190, 815740520, 
  689809286, 711327114, 658017649, 636727234, 871088534, 964608547, 867960437, 964911023, 
  642411618, 868318236, 793328473, 849540177, 960039699, 998262224, 775720601, 634685437, 
  743766982, 826321850, 846671921, 712570181, 676890302, 814283264, 958273130, 899003369, 
  909973864, 921987721, 978601888, 633027021, 896400011, 725078407, 662183572, 629843174, 
  617774786, 695823011 };
	vector <int> p1(t1, t1+sizeof(t1)/sizeof(int));
	WorldPeace * obj = new WorldPeace();
	clock_t start = clock();
	long long my_answer = obj->numGroups(p0, p1);
	clock_t end = clock();
	delete obj;
	cout <<"Time: " <<(double)(end-start)/CLOCKS_PER_SEC <<" seconds" <<endl;
	long long p2 = 3983180234LL;
	cout <<"Desired answer: " <<endl;
	cout <<"\t" << p2 <<endl;
	cout <<"Your answer: " <<endl;
	cout <<"\t" << my_answer <<endl;
	if (p2 != my_answer) {
		cout <<"DOESN'T MATCH!!!!" <<endl <<endl;
		return -1;
	}
	else {
		cout <<"Match :-)" <<endl <<endl;
		return (double)(end-start)/CLOCKS_PER_SEC;
	}
}

int main() {
	int time;
	bool errors = false;
	
	time = test0();
	if (time < 0)
		errors = true;
	
	time = test1();
	if (time < 0)
		errors = true;
	
	time = test2();
	if (time < 0)
		errors = true;
	
	time = test3();
	if (time < 0)
		errors = true;
	
	time = test4();
	if (time < 0)
		errors = true;
	
	if (!errors)
		cout <<"You're a stud (at least on the example cases)!" <<endl;
	else
		cout <<"Some of the test cases had errors." <<endl;
}

//Powered by [KawigiEdit] 2.0!
